#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;

string longestPalindrome(string s) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function

    // construct count and dumpS
    if(s.size() == 0)
        return "";
    if(s.size() == 1)
        return s;
    vector<int> count;
    vector<char> dumpS;
    dumpS.push_back(s[0]);
    count.push_back(1);
    for(int i=1; i<s.length(); ++i){
        if(s[i] != *(dumpS.end()-1)){
            dumpS.push_back(s[i]);
            count.push_back(1);
        }
        else{
            *(count.end()-1) += 1;
        }
    }
    // loop
    int maxLength = count[0];
    int maxIndexInDump = 0;
    int lastMatch = count[0];
    set<int> readSet;
    set<int> writeSet;
    set<int> *pRead = &readSet;
    set<int> *pWrite = &writeSet;
    readSet.insert(1);
    for(int i=1; i<dumpS.size(); ++i){
        // not self center
        pWrite->clear();
        // existing length
        for(set<int>::iterator it = pRead->begin();
            it != pRead->end();
            ++it){
                int existLength = *it;
                int curIndex = i-1;
                while(curIndex>=0 && existLength>0){
                    existLength -= count[curIndex];
                    --curIndex;
                }
                if(existLength < 0){
                    continue;
                }
                if(curIndex >= 0 && dumpS[i] == dumpS[curIndex]){
                    int matchNum = count[curIndex] > count[i] ? count[i] : count[curIndex];
                    int newLength = *it + matchNum * 2;
                    pWrite->insert(newLength);
                    // update max
                    if(newLength > maxLength){
                        maxLength = newLength;
                        maxIndexInDump = i;
                        lastMatch = matchNum;
                    }
                }
        }
        // self
        pWrite->insert(count[i]);
        if(count[i] > maxLength){
            maxLength = count[i];
            maxIndexInDump = i;
            lastMatch = count[i];
        }
        set<int> *pTmp = pWrite;
        pWrite = pRead;
        pRead = pTmp;
    }
    // get the result
    int sum = 0;
    for(int i=0; i< maxIndexInDump; ++i)
        sum += count[i];
    int end = sum - 1 + lastMatch;
    int begin = end - maxLength + 1;
    return s.substr(begin, end-begin+1);

}



int main(){

    cout<< longestPalindrome("bb")<<endl;

    return 0;
}